package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder
import java.util.*

/**
https://leetcode.cn/problems/merge-two-binary-trees/description/

题型： 前序遍历

617. 合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。

示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
 */
class leetcode_617 {
    @Test
    fun test_1() {
        val root1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n5 = TreeNode(5)
        root1.left = n3
        root1.right = n2
        n3.left = n5

        val root2 = TreeNode(2)
        val n1 = TreeNode(1)
        val n3_v2 = TreeNode(3)
        val n4 = TreeNode(4)
        val n7 = TreeNode(7)
        root2.left = n1
        root2.right = n3_v2
        n1.right = n4
        n3_v2.right = n7

        val root3 = mergeTrees(root1, root2)
        val actual = printLevelOrder(root3)
        val expect = arrayListOf(arrayListOf(3), arrayListOf(4, 5), arrayListOf(5, 4, 7))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val root1 = TreeNode(1)
        val root2 = TreeNode(1)
        root2.left = TreeNode(2)
        val root3 = mergeTrees(root1, root2)
        val actual = printLevelOrder(root3)
        val expect = arrayListOf(arrayListOf(2), arrayListOf(2))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    private fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
        // 构建左孩子时，判断它们的左孩子是否为空，若一方为空，则直接返回另一方，否则相加
        // 构建右孩子时，判断它们的右孩子是否为空，若一方为空，则直接返回另一方，否则相加
        // return mergeTrees1(root1,root2)
        return mergeTrees2(root1, root2)
    }

    private fun mergeTrees1(root1: TreeNode?, root2: TreeNode?): TreeNode? {
        // 前序遍历 - 递归
        // T - N
        // S - H

        // 1 确定函数的参数以及返回值
        // 2 确定终止条件
        if (null == root1 && null == root2) {
            return null
        }
        if (null != root1 && null == root2) {
            return root1
        }
        if (null == root1 && null != root2) {
            return root2
        }

        // 3 确定单层递归的处理逻辑：前序遍历
        // 调整中的位置，可以变成中序遍历和后序遍历
        // 此处重用了root1作为返回值，还可以使用新建节点作为返回值
        if(root1 != null && root2 != null){
            // 中
            root1.`val` = root1.`val` + root2.`val`
            // TODO:容易漏掉 root1.left
            // 左
            root1.left = mergeTrees(root1.left, root2.left)

            // TODO:容易漏掉 root1.right
            // 右
            root1.right = mergeTrees(root1.right, root2.right)

        }
        return root1
    }

    private fun mergeTrees2(root1: TreeNode?, root2: TreeNode?): TreeNode? {
        // 层级遍历 - 迭代
        if (null == root1 && null == root2) {
            return null
        }
        if (null == root1 && null != root2) {
            return root2
        }
        if (null != root1 && null == root2) {
            return root1
        }

        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root1)
        queue.offer(root2)

        while (!queue.isEmpty()) {
            val node1 = queue.poll()
            val node2 = queue.poll()
            node1.`val` = node1.`val` + node2.`val`

            if (node1.left != null && node2.left != null) {
                queue.offer(node1.left)
                queue.offer(node2.left)
            } else if (node1.left != null && node2.left == null) {
                // 不用处理
            } else if (node1.left == null && node2.left != null) {
                node1.left = node2.left
            }

            if (node1.right != null && node2.right != null) {
                queue.offer(node1.right)
                queue.offer(node2.right)
            } else if (node1.right != null && node2.right == null) {
                //  不用处理
            } else if (node1.right == null && node2.right != null) {
                node1.right = node2.right
            }
        }
        return root1
    }
}